package com.ljy.my_study.leetcode.下一个排列;

import java.util.Arrays;

/**
 * @author lijunying
 * @date 2021/1/11 8:50
 */
public class TestMain {

//    实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
//
//    如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
//
//    必须 原地 修改，只允许使用额外常数空间。
//
//             
//
//    示例 1：
//
//    输入：nums = [1,2,3]
//    输出：[1,3,2]
//    示例 2：
//
//    输入：nums = [3,2,1]
//    输出：[1,2,3]
//    示例 3：
//
//    输入：nums = [1,1,5]
//    输出：[1,5,1]
//    示例 4：
//
//    输入：nums = [1]
//    输出：[1]
//             
//
//    提示：
//
//            1 <= nums.length <= 100
//            0 <= nums[i] <= 100
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/next-permutation

    public static void main(String[] args) {
//        int[] nums=new int[]{1,2,5,4,6,3,2,3,1};
        int[] nums=new int[]{1,3,2};
//        int[] nums=new int[]{1,2,2,4,3,2};
        new TestMain().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void nextPermutation(int[] nums) {
        boolean isChange=false;
        int index=nums.length-1;
        for(int i=nums.length-1;i>0;i--){
            if(nums[i]>nums[i-1]){
//                int flag=nums[i];
//                nums[i]=nums[i-1];
//                nums[i-1]=flag;
                index=i;
                changeValue(nums,index);
                isChange=true;
                break;
            }
        }
        if(!isChange&&index==nums.length-1){
            index=0;
        }
        sort(nums,index);
    }

    private void sort(int[] nums,int start){
        Arrays.sort(nums,start,nums.length);
    }

    private void changeValue(int[] nums,int index){
        int nextIndex=index;
        for(int i=index+1;i<nums.length;i++){
            if(nums[i]>nums[index-1]&&nums[i]<nums[index]){
                nextIndex=i;
            }
        }
        int flag=nums[nextIndex];
        nums[nextIndex]=nums[index-1];
        nums[index-1]=flag;
    }
}
